# 给你一个 m x n 的矩阵 board ，由若干字符 'X' 和 'O' ，找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。
#
#  示例 1：
# 输入：board = [
# ["X","X","X","X"],
# ["X","O","O","X"],
# ["X","X","O","X"],
# ["X","O","X","X"]]
# 输出：[
# ["X","X","X","X"],
# ["X","X","X","X"],
# ["X","X","X","X"],
# ["X","O","X","X"]]
# 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都
# 会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
#
#  示例 2：
# 输入：board = [["X"]]
# 输出：[["X"]]
from typing import List


class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        首先在边界(四周)使用dfs将能与边界"相连的"所有'O'替换成'*'
        然后遍历数组，把'O'变为'X'（因为不和边界相连），把'*'变为'O'（因为和边界相连）即可
        :param board:
        :return:
        """
        directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]
        m, n = len(board), len(board[0])

        def dfs(i: int, j: int) -> None:
            if 0 <= i < m and 0 <= j < n and board[i][j] == 'O':
                board[i][j] = '*'
                for x, y in directions:
                    if 0 <= i + x < m and 0 <= j + y < n:
                        dfs(i + x, j + y)

        for row in range(m):  # 将能与第一列或者最后一列“相连”的'0'用'*'替换
            dfs(row, 0)  # 第一列
            dfs(row, n - 1)  # 最后一列
        for column in range(n):  # 将能与第一行或者最后一行“相连”的'0'用'*'替换
            dfs(0, column)  # 第一行
            dfs(m - 1, column)  # 最后一行

        for row in range(m):  # 遍历数组，把'O'变为'X'（因为不和边界相连），把'*'变为'O'（因为和边界相连）
            for column in range(n):
                if board[row][column] == 'O':
                    board[row][column] = 'X'
                if board[row][column] == '*':
                    board[row][column] = 'O'


if __name__ == "__main__":
    # board = [
    #     ["X", "X", "X", "X"],
    #     ["X", "O", "O", "X"],
    #     ["X", "X", "O", "X"],
    #     ["X", "O", "X", "X"]]
    board = [["O", "O"], ["O", "O"]]
    board = [["O"]]
    Solution().solve(board)
    for row in board:
        print(row)
